高级语言怎么来的（六）：Scheme 语言是怎么来的

#Technomous #Lisp #PL

Scheme 是 LISP 的一个方言（dialect）。著名的 SICP 书就是以 Scheme 为教学语言（实际上 SICP 的作者就是 Scheme 的作者）。虽然 Scheme 本身只是一个精简化的适合教学的语言，可它首先提出的一些重要的思想，引领了新一代的 LISP 语言的出现。实际上，LISP 语言发展的历史是连续的，之所以我在这里人为的把 LISP 的发展史划分为上一代和现代，是因为随着 Scheme 首次引入并规范化了一些重要概念，LISP 语言出现了很多以前从来没有大规模普及的新特性。以 Common LISP 为代表的 LISP 语言也因为这些新特性，而焕发了第二春。人所共知的 Paul Graham 大叔，借着这一波 LISP 复兴的浪潮，不光写出了 On Lisp 这样的好书；而且还用 Common LISP 写出了一个在线电子商务平台，在 1998 年的时候以近 5 千万美元的价格卖给了 Yahoo! （凭借这笔买卖，Paul 大叔现在经营着 Y Combinator 天使投资，成为硅谷著名的天使）。前段时间卖给 Google 的 ITA，负担着世界上大部分的航班资讯查询，核心系统也是 Common LISP。虽然不该把 Common LISP 的很多成就全部归结到 Scheme，但 Scheme 作为一个重要的历史分水岭，探究一下它的历史来源还是很有趣的。

函数作为一级对象

我们都知道 LISP 是一个函数式的编程语言。在 LISP 中，函数是一种基本类型。类比的看，C 家族的语言中，整数是一个基本的类型，所以，整数类型的变量既可以作为参数传递给一个函数，也可以作为返回值返回。比如，两个整数求和这个函数，用 C 家族的语法就是

int add(int a, int b);

因为在 LISP 里面，函数也成了基本类型。如果我们有一个 add 函数如下：

(define (add x y) (+ x y))

显然，它在 LISP 里就和 C 里的 int 一样，能够作为参数传递给其他函数。

函数作为参数在 LISP 里非常普遍。我们知道著名的 APPLY MAP 和 REDUCE 这三个“高阶”函数（所谓高阶的意义就是参数可以是函数）。其中 APPLY 的最基本形式可以带两个参数，第一个参数是函数，第二个参数是一个列表。APPLY 的效果就是把这个列表作为参数表，送给第一个参数所代表的函数求值。如果我们在 LISP 里面用 APPLY(add, (1, 2)) 结果就是 3，即把 (1,2) 送给 add 作为参数，结果自然是 3。这是函数作为参数的例子，还有函数作为返回值的例子就不一一列举了。

自由变量的幽灵

在 add 这个函数的定义中我们可以看到，它的结果和两个输入值 x，y 有关。如果我们用 add(1,2) 调用 add 函数，我们至少期望变量 x 会被赋值为 1，变量 y 被赋值为 2。而结果 (+ x y) 则相应的为 3。在这个简单的例子中，显然，如果 x 和 y 有一个值不知道的话，(+ x y) 的计算就无法完成。我们暂且把这些对函数求值不可缺少的变量称之为“必要变量”。显然，这些必要变量的值是需要确定的，否则函数无法进行求值。在我们 add 函数的例子里，x，y 这两个变量既是全部的必要变量，又是这个函数的参数，所以这个函数的结果就完全由输入的 x，y 的值确定。可以想象，任何一个像 add 这样的所有的必要变量都是来自于输入参数的函数，不论在什么地方被调用，只要输入的参数值一样，输出的结果必然一样。

如果现实中所有的函数都有上面的性质的话，那就没有这篇文章了。可惜的是我们很快发现有好多函数不符合上面我们说的“输入的参数值一样，输出的结果必然一样”这个结论。我们甚至无须用 LISP 里面的例子来说明这一点。用 C 语言的都知道，取系统当前时间的函数 time，以及取随机数的函数 rand，都是不需要输入值（0个输入参数）。因此任何时候这两个函数被调用的时候，我们都可以认为输入值一样（为 void 或 null）。但我们在不同的时间调用 time 或者多次调用 rand，很显然可以知道他们输出的结果不可能每次一样。

函数式编程里面有更多的类似的例子。这些例子说明了的确有些函数，对于同样的输入值，能够得到不同的结果。这就很显然的表明，这些函数的必要变量中，有些不是函数的输入参数或者内部变量。我们把这些变量，叫做自由变量（free variable ）相反的那些被成为受限变量（bounded variable）。这里的自由和受限，都是相对函数讲的，以变量的取值是不是由函数本身决定来划分的。

虽然自由和受限变量是函数式语言里面的概念，但在命令式语言中也有影子。比方说，C 语言中，函数中用到的全局变量就是自由变量；在 Java 程序中，匿名内部类里面的方法可以用到所在外部类中的成员变量或者所在方法里标记为 final 的那些变量。这些可以被内部类的方法访问的，又不在内部类方法的参数表里面的变量都是自由变量。乐意翻看 GNU C Library 的好奇读者会看到，GNU libc 中的 rand 函数就用到了一个 random_data 的变量作为自由变量 （glibc/stdlib/random.c）。time 也是一样，通过一个系统调用来设置时间，而这在原理上等价于用到一个叫做”当前时间”的自由变量 （glibc/stdlib/time/time.c）。

我们知道，在高级语言里面仅仅设计或者加入一个特性不难，难的是让所有的特性能协调一致的工作。比方说 Java 语言假设一切均为为对象，容器类型也假设装着对象，但是 int 类型却不是对象，让无数程序员为装箱拆箱大汗淋漓。回到 LISP，当函数允许自由变量，函数有能够被作为参数传来传去的时候，自由变量的幽灵就随着函数作为参数传递而在程序各处游荡。这就带来了两个问题，一个涉及到自由变量的值的确定机制，另一个涉及到这个机制的实现。

两种作用域

为了说明自由变量的幽灵和作用域，我们还是从一个例子入手。假设我们要一个做加 n 的函数。为了体现出自由变量，我们把它写成

(define (addn s) (lambda x (+ x s)))

这个函数本身没什么特别的：输入一个 s，输出一个对任意 x 返回 x＋s 的函数。注意到这个函数的“返回值”是一个函数。基于这个 addn 函数，我们可以定义 ＋1 函数 add1 函数如下，

(define (add1 s) ((addn 1) s))

这个也很好解释，如果输入一个 s， (addn 1) 返回了一个加一函数，这个函数作用在 s 上，即可得到 s+1。一切看上去很顺利，直到我们用一个 Scheme 出现前的 LISP 解析器去计算 (add1 4)。 我们期望得到的值是 5， 而它给你的值可能是 8。怎么回事？

为了解释这个 8 的来源，我们可以模拟一下一个基于栈的解释器的工作过程。(add1 4) 调用首先将参数 s 赋值为 4 然后，展开 add1 函数，即将 s=4 压栈，计算 (addn 1)。在调用 addn 时。s 又作为了 addn 的形式参数。因此，按照基于栈的解释器的标准做法，我们在一个新的活动窗口中将 s =1 压栈。addn 这个函数返回的是一个 “lambda x (+ x s)” 的函数，其中 s 是自由变量。然而一旦 addn 返回，栈中的 s=1 就会被弹出。当我们把这个返回了的 lambda 表达式作用到 4 上求值时候，x 是这个 lambda 表达式传入的形式参数，赋值为 4，栈里面的 s 的值只有 s=4，因此 (+ x s) 得到的是 8。

这显然不是我们想要的。总结这个结果错了的原因，是因为我们的解释器没有限定 lambda x (+ x s) 里面的自由变量 s 为 1。 而是在计算这个 lambda 表达式的时候才去查找这个自由变量的值。自由变量的幽灵在函数上开了一个后门，而我们没有在我们想要的地方堵上它，让它在函数真正求值的时候泄漏出来。

我们不是第一个发现这个问题的人。实际上，LISP 刚出来没多久，就有人向 LISP 的发明人 John McCarthy 报告了这个 “BUG”。John 也认为这是一个小 BUG，就把球踢给了当时写 LISP 实现的 Steve Russell。此人我之前的文章介绍过，乃是一个水平很高的程序猿（Code Monkey）。他认识到，这个问题的来源，在于返回的 lambda 表达式失去了不应该失去的确定它自由变量值的环境信息，在求值的时候，这些环境信息应该跟着这个 lambda 表达式一起。这样才能保证没有这个 BUG。不过 lambda 表达式在 LISP 语言中已经成型了，所以他就引入了一个新叫做 FUNCTION 的修饰符。作为参数的 lambda 表达式或函数要改写成 (FUNCTION lambda) 。这样，这个 lambda 表达式在被 eval 解析的时候就会被标记成 FUNARG，并且静态绑定到解析时所在环境。而用 APPLY 对函数求值时，有 FUNARG 标签的函数会在当时绑定的环境中求值，而不是在当前环境中求值。自由变量没有到处乱跑，而是被限制在了当时绑定的环境里面。Russell 的这个巧妙设计，成功关闭了自由变量在函数上开的口。这种加上了环境的函数就既能够被四处传递，而不需要担心自由变量的幽灵到处乱串。这个东西，后来就被称为“闭包”。Russell 用 FUNCTION，以用一种“装饰”的方式，在 LISP 1.5 中第一次引入和实现和闭包。

在编程语言的术语中，上面的让自由变量自由自在的在运行时赋值的机制，一般叫做动态作用域（dynamic scope），而让函数和确定自由变量值在解析时静态绑定的机制，一般称之为静态作用域（static dynamic scope）。既然是静态绑定的环境是解析的时候确定的，而解析器是逐行解析程序的，所以，静态作用域的环境是完全由程序代码的结构确定的。因此有时候静态作用域又被等价的称为“文法作用域”（lexical scope）。上面我们的例子里。我们的真正意图是使用静态作用域，却遇到了一个使用动态作用域的 LISP 解析器，因此出现了 (add1 4) 等于 8 的错误。但这个问题并不足以说明静态作用域一定好。动态作用域的问题，关键在于违反了 Alpha 变换原则和封装原则，不过不在此详细展开了。

后续的几小节提要